logo móvil
Contáctanos

Un algoritmo de detección de quasi-huecos para reconocer grafos hereditarios de distancia, con < 2

Autores: Cicerone, Serafino

Idioma: Inglés

Editor: MDPI

Año: 2021

Descargar PDF

Acceso abierto

Artículo científico
2021

Un algoritmo de detección de quasi-huecos para reconocer grafos hereditarios de distancia, con < 2


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Gráficos
Hereditario en distancia
Subgráficos
Propiedades de ciclo-cuerda
Algoritmo de reconocimiento
Cuasi-agujeros

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 32

Citaciones: Sin citaciones


Descripción
Cicerone y Di Stefano definieron y estudiaron la clase de grafos hereditarios por distancia, es decir, grafos donde la distancia en cada subgrafo inducido conectado es a lo sumo veces la distancia en todo el grafo. Los grafos definidos representan una generalización de los conocidos grafos hereditarios por distancia, que en realidad corresponden a grafos hereditarios por distancia 1. En este artículo avanzamos en el estudio de estos nuevos grafos proporcionando caracterizaciones para la clase de todos los grafos hereditarios por distancia tales que. Las nuevas caracterizaciones se dan en términos de subgrafos prohibidos y propiedades de ciclo-cuerda. Estos resultados también conducen a idear un algoritmo de reconocimiento en tiempo polinómico para este tipo de grafo que, de acuerdo con las caracterizaciones proporcionadas, simplemente detecta la presencia de cuasi-agujeros en cualquier grafo dado.

Otros recursos que podrían interesarte

Temas Virtualpro